package or;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class T1096 {


    String expression;
    int idx;

    public List<String> braceExpansionII(String expression) {
        this.expression = expression;
        this.idx = 0;
        Set<String> ret = expr();
        return new ArrayList<String>(ret);
    }


    public Set<String> item(){
        Set<String> strs=new TreeSet<>();
        if(expression.charAt(idx)=='{'){
            idx++;
            strs=expr();
        }else {
            strs.add(expression.substring(idx,idx+1));
        }

        idx++;
        return strs;
    }
    public Set<String> term(){
        Set<String> strs=new TreeSet<>();
        strs.add("");
        while (idx<expression.length()&&(expression.charAt(idx)=='{'||Character.isLetter(expression.charAt(idx)))){
            Set<String> t=item();
            Set<String> temp=new TreeSet<>();
            for(String str1:strs){
                for(String str2:t){
                    temp.add(str1+str2);
                }
            }
            strs=temp;
        }
        return strs;
    }
    public Set<String> expr(){
        Set<String> strs=new TreeSet<>();

        while (true){
            strs.addAll(term()) ;
            if (idx<expression.length()&&expression.charAt(idx)==','){
                idx++;
                continue;
            }else {
                break;
            }
        }
        return strs;
    }


    @Test
    public void test() {

        String str="{a,b}{c,{d,e}}";
        List<String> ret =braceExpansionII(str);
        System.out.println(ret.toString());


    }


}
